「算法思想」《编程珠玑》学习笔记
0x00 前言
本文是对《编程珠玑》一书的学习笔记。
第一部分 基础
0x01 开篇
确定用户的真实需求是程序设计的根本。
本章围绕下面这个问题展开：
- 如何给磁盘文件排序？文件最多包含1000万条记录，每个记录都是7位的整数。
1. 学会准确描述问题
在试图解决这个问题之前，先将已知条件组织成一种更客观、更易用的形式。
- 输入：n个正整数，且每个数都小于n，其中 $n=10^7$ ，保证没有重复。
- 输出：按升序排列的输入整数的列表。
- 约束：最多有1MB的内存可用，有足够多的磁盘空间，运行时间要求在10s内。
2. 程序设计 - 位图法
该排序问题的特殊性在于对内存的限制，1000万条7位记录，至少也需要大约 $10^7B = 10MB$ 。
- 一种显而易见的方法是基于磁盘的归并排序，但显然满足不了运行时间限制。
- 另一种方法是多趟排序，若每个7位正整数都用32位整数（int型）来表示的话，1MB内存就可以存储25w个，因此可以遍历输入文件40趟来完成排序。
文中提到了一种更加巧妙地方法，$1MB$ 的空间大约有800万个可用位，要表示最多1000万个互异的整数，由此，考虑使用位图来表示集合。例如，可用一个8位长的字符串来表示一个所有元素都小于8的非负整数集合，类似独热编码。
{1, 2, 3, 5}:
0 1 1 1 0 1 0 0
因此，我们使用一个具有1000万个位的字符串来表示输入文件，当且仅当整数 $i$ 在文件中存在时，第 $i$ 位为 $1$ 。伪代码如下：
1 | // initialize set to empty |
拓展思考
- 对于实际测试环境，需要考虑错误处理，如：重复数字、输入整数小于0或大于n等等
0x02 啊哈！算法
“看起来很困难的问题也可以有一个简单的、意想不到的答案。” —— 《啊哈！灵机一动》
本章围绕三个小问题展开：
给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。
将一个n元一维向量向左旋转 $i$ 个位置（即循环移位），要求在 $O(n)$ 时间内完成。
例如，当 $n=8, i=3$ 时，向量 $abcdefgh$ 旋转为 $defghabc$ 。
给定一个英语字典，找出其中的所有变位词集合。
例如，”post”、”stop”、”tops” 互为变位词。
1. 无处不在的二分搜索
暴力搜索？
当具有足够的内存时，最直接的方法便是先快排序再遍历一遍。但如果只有几百字节的内存和几个外部的“临时”文件可用，又该如何解决该问题呢？
试试二分搜索
二分搜索最常见的应用是在有序数组中搜索元素，但问题1中的整数是随机排列的，这就使得答案并不那么显而易见。
为了采用二分搜索技术，就必须定义一个范围、在该范围内表示元素的方式以及用来确定哪一半范围存在缺失整数的探测方法。
【进一步明确问题】
给定一个长度为n-1的随机排列的数组，所有数字唯一且都在0~n的范围内（ $n<2^{32}$ ），找出不在这个数组中的数字。
【灵机一动的结果】
我们可以通过统计中间点之上和之下的元素来探测范围，但如何确定中间点呢？如果我们换一个角度来看的话，会发现这些整数几乎覆盖了从 0x0000 0000 到 0xffff ffff 的数，这些数的中间点是什么？显然，是最高位为1的数，即0x8000 0000。
至此，问题的答案已经呼之欲出了：
- 范围：包含至少一个缺失元素的一系列整数。
- 表示元素的方式：32位二进制整数
- 确定范围的探测方法：
- 对该范围内的所有整数，从最高位起进行0/1探测，并把位为0和位为1的整数分别保存在两个文件中；
- 比较两个文件的中整数的数量，缺少的那个整数一定存在于较少的那个文件中。
【示例】
我们以0~15为范围，这些数最多只占4比特，假设缺少整数8（1000）。
- 我们把0～15这些数按最高位（第3位）分为0/1两份，这样最高位为1的数就会比最高位为0的数的个数少一个，由此可断定缺少的数在保存1的文件中；
- 进一步把文件1中的数按第2位分为0/1两份，此时为0的数会比为1的数少一个，依此类推。
2. 基本操作的威力
问题2的旋转操作可以有很多种解法
两种暴力解法
- 首先将x的前i个元素复制到一个临时数组中，然后将余下的n-i个元素向左移动i个位置，最后将最初的i个元素从临时数组中复制到x中余下的位置。
- 定义一个函数将x向左旋转（平移）一个位置，然后调用该函数i次，但该方法时间复杂度为 $O(in)$ 。
*来个绝活！
按书中的说辞，这种方法「有点像精巧的杂技动作」：
- 移动 $x[0]$ 到临时变量 $t$ ，然后移动 $x[i]$ 至 $x[0]$ ，$x[2i]$ 至 $x[i]$ ，依次类推，直至返回到取 $x[0]$ 中的元素，此时改为从 $t$ 取值，然后终止过程。
当 $i$ 为 3 且 $n$ 为 12 时，元素按如下顺序移动。
这种思想有点类似 i-路组相联映射，即每组大小为 $i$ ，总共 $n/i = k$ 组，然后按组平移：先平移每组的第一个元素，再平移第二个… 显然时间复杂度为 $O(n)$ 。
但有个问题，如果 $n$ = 13 时，该怎么移动呢？
重点：翻转算法
从另外一名考察这个问题，可以得到一个不同的算法：
- 旋转向量 $x$ 其实就是交换向量 $ab$ 的两段，得到向量 $ba$ ，这里 $a$ 代表 $x$ 中的前 $i$ 个元素。
- 假设 $a$ 比 $b$ 短，将 $b$ 分为 $b_l$ 和 $b_r$ ，使得 $b_r$ 长度也为 $i$ ，交换 $a$ 和 $b_r$ ，也就将向量 $ab_lb_r$ 转换为 $b_rb_la$ 。
- 此时序列 $a$ 已处于最终的位置，因此只需交换 $b$ 的两部分，显然这个是原来的子问题，因此可以递归解之。
【翻转算法】
- 首先对 $a$ 求逆，得到 $a^rb$ ；
- 然后对 $b$ 求逆，得到 $a^rb^r$ ；
- 最后整体求逆，得到 $(a^rb^r)^r$ ，亦即 $ba$ 。
于是可得下列翻转代码，注释表示翻转以后的结果。
1 | reverse(0, i-1) /* cbadefgh */ |
进一步有，$cba = (a^rb^rc^r)^r$ 。实际上，很多文本编辑器都是使用翻转算法实现了行的移动。
3. 排序
灵机一动的结果就是标识字典中的每一个词，使得相同的变位词具有相同的标识。
我最开始的想法是受到
0x01 开篇/2.程序设计 - 位图法的启发，用一个26位的整数来标识每一类变位词。当某个单词中存在某个字母时，对应位为1。但这种标识方法忽略了字母是可以重复的，如 tree 。
那么变位词问题将简化为两个子问题：选择标识和集中具有相同标识的单词。
- 解决第一个问题：我们可以使用基于排序的标识，将单词中的字母按照字母表顺序排列，如 “deposit” 的标识就是 “deiopst”。
- 解决第二个问题：我们将所有的单词按照其表示的顺序排序。
0x03 数据决定程序结构
恰当的数据视图实际上决定了程序的结构，很多程序都可以通过重新组织内部数据而变得更加简洁高效。
这里只摘录一个「格式信函模板」的例子。
当我们登录某个网页时，可能会弹出如下页面：
1 | Welcome back, Jay! |
一个急躁的程序员可能会试图按照下面的方式编写代码：
1 | read lastname, firstname, init, title, streetnum, streetname, town, state, zip |
一个更加巧秒的方法是编写一个格式信函模板：
1 | Welcome back, $1! |
符号 $$i$ 代表记录中的第 $i$ 个字段，文字符号 $$$ 在输入模板中记为 $$$$ 。
1 | read fields from database |
0x04-0x05 编写正确的程序
代码的开发是自上而下进行的（从一般思想开始，将其完善为独立的代码行），该正确性分析则是自下而上进行的：从每个独立的代码行开始，检查它们是如何协同运作并解决问题的。
前面三章讨论过的主题：问题定义、算法设计以及数据结构选择。如果这些步骤都完成得很好，那么编写正确的程序通常是很容易的。
这里只摘录部分程序验证的一般性原理：
断言
输入、程序变量和输出之间的关系勾勒出了程序的“状态”，断言使得程序员可以准确阐述这些关系。
我们使用
assert表示我们相信某个逻辑表达式为真。语句assert n>=0在n为0或大于0时什么都不做，但当n为负值时会报告某种错误。函数
要验证一个函数，首先需要使用两个断言来陈述其目的。前置条件（precondition）是在调用该函数之前就应该成立的状态，后置条件（postcondition）地正确性由函数在终止执行时保证。比如二分搜索函数：
1
2
3
4
5
6int bsearch(int t, int x[], int n)
/* precondition: x[0] <= x[1] <= ... <= x[n-1]
postcondition:
result == -1 => t not present in x
0 <= result < n => x[result] == t
*/一旦证明函数体具有该性质，在以后的应用中就可以直接使用前置条件和后置条件之间的关系而不再需要考虑其实现。该方法在软件开发中通常称为“契约编程”。
调试
略
在编写测试程序时，使用 printf 语句报告测试进度可能仅得到一些混乱且非实质性的信息，因此可尝试使用 assert 代替之。
第二部分 性能
